import java.awt.Color;

public class SeamCarver {
	private Picture mPicture;
	private int     mHeight;
	private int     mWidth;
	private int[][] mEnergy;
	
	public SeamCarver(Picture picture) {
		mPicture = new Picture(picture);
		mHeight  = mPicture.height();
		mWidth   = mPicture.width();
		mEnergy  = new int[mWidth][mHeight];
		initEnergy();
	}
	
	private void initEnergy()
	{
		for(int x = 0; x < mWidth; x++)
			for(int y = 0; y < mHeight; y++)
				if(x == 0 || x == mWidth - 1 || y == 0 || y == mHeight - 1)
					mEnergy[x][y] = 195075;
				else
					mEnergy[x][y] = energy_x(x,y) + energy_y(x,y);
	}
	
	public Picture picture() {
		return mPicture;
	}

	public int width() {
		return mWidth;
	}

	public int height() {
		return mHeight;
	}
	
	static private int pow2(int x)
	{
		return x*x;
	}
	
	static private int energy(Color c1, Color c0)
	{
		return pow2(c1.getRed() - c0.getRed()) + pow2(c1.getBlue() - c0.getBlue()) + pow2(c1.getGreen() - c0.getGreen());
	}

	private int energy_x(int x, int y) {
		return energy(mPicture.get(x + 1, y), mPicture.get(x - 1, y));
	}
	
	private int energy_y(int x, int y) {
		return energy(mPicture.get(x,y+1), mPicture.get(x,y-1));
	}
	
	public double energy(int x, int y) {
		if(x < 0 || x >= mWidth || y < 0 || y >= mHeight)
			throw new IndexOutOfBoundsException();
		
		return mEnergy[x][y];
//		if(x == 0 || x == mWidth - 1 || y == 0 || y == mHeight - 1)
//			return 195075.0;
		
//		return energy_x(x,y) + energy_y(x,y);
	}
	
	private class SeamState {
		final double[][] weight    = new double[mWidth][mHeight];
		final int[][]    pathFromX = new int[mWidth][mHeight];
		final int[][]    pathFromY = new int[mWidth][mHeight];
		
		public SeamState()
		{
			for(int yi = 0; yi < mHeight; yi++)
				for(int xi = 0; xi < mWidth; xi++)
					weight[xi][yi] = Double.MAX_VALUE;
		}
		
		public void update(int xi, int yi, int xnext, int ynext)
		{
			if(xnext < 0 || xnext >= mWidth || ynext < 0 || ynext >= mHeight)
				return;
			
			double w = weight[xi][yi] + energy(xnext,ynext);
			
			if(w < weight[xnext][ynext])
			{
				weight[xnext][ynext]    = w;
				pathFromX[xnext][ynext] = xi;
				pathFromY[xnext][ynext] = yi;
			}
		}
	}

	public int[] findVerticalSeam() {
		
		final SeamState state = new SeamState();

		for(int xi = 0; xi < mWidth; xi++)
			state.weight[xi][0] = 0;
		
		for(int yi = 0; yi < mHeight - 1; yi++) {
			for(int xi = 0; xi < mWidth; xi++) {
				state.update(xi, yi, xi-1, yi+1);
				state.update(xi, yi, xi+0, yi+1);
				state.update(xi, yi, xi+1, yi+1);
			}
		}
		
		final int last_row = mHeight-1;
		
		int    min_ind = -1;
		double min_arg = Double.MAX_VALUE; // state.weight[0][mHeight-1];

		//StdOut.println("Last row:");
		for(int i = 0; i < mWidth; i++) {
			//StdOut.println(state.weight[i][last_row]);
			if(state.weight[i][last_row] < min_arg) {
				min_arg = state.weight[i][last_row];
				min_ind = i;
			}
		}
		
		int[] result = new int[mHeight];
		
		for(int h = mHeight-1; h >= 0; h--) {
			result[h] = min_ind;
			min_ind = state.pathFromX[min_ind][h];
		}
		
		return result;
	}

	public int[] findHorizontalSeam() {
		final SeamState state = new SeamState();
		
		for(int yi = 0; yi < mHeight; yi++)
			state.weight[0][yi] = 0;

		for(int xi = 0; xi < mWidth - 1; xi++) {
			for(int yi = 0; yi < mHeight; yi++) {
				state.update(xi, yi, xi+1, yi-1);
				state.update(xi, yi, xi+1, yi+0);
				state.update(xi, yi, xi+1, yi+1);
			}
		}
		
		final int last_col = mWidth-1;
		
		int    min_ind = -1;
		double min_arg = Double.MAX_VALUE; // state.weight[0][height()-1];

		//StdOut.println("Last col:");
		for(int i = 0; i < mHeight; i++) {
			//StdOut.println(state.weight[last_col][i]);
			if(state.weight[last_col][i] < min_arg) {
				min_arg = state.weight[last_col][i];
				min_ind = i;
			}
		}
		
		int[] result = new int[mWidth];
		
		for(int w = mWidth-1; w >= 0; w--) {
			result[w] = min_ind;
			min_ind = state.pathFromY[w][min_ind];
		}
		
		return result;
	}

	public void removeHorizontalSeam(int[] a) {
		if(a.length != mWidth)
			throw new java.lang.IllegalArgumentException();

		Picture newPicture = new Picture(mWidth, mHeight-1);
		
		for(int xi = 0; xi < mWidth; xi++) {
			for(int yi = 0, nyi = 0; yi < mHeight; yi++) {
				if(a[xi] != yi) {
					newPicture.set(xi, nyi, mPicture.get(xi, yi));
					nyi++;
				}
			}
		}
		mPicture = newPicture;
		mHeight  = mPicture.height();
		mWidth   = mPicture.width();
		initEnergy();
	}

	public void removeVerticalSeam(int[] a) {
		
		if(a.length != mHeight)
			throw new java.lang.IllegalArgumentException();
		
		final Picture newPicture = new Picture(mWidth-1, mHeight);
		
		for(int yi = 0; yi < mHeight; yi++) {
			for(int xi = 0, nxi = 0; xi < mWidth; xi++) {
				if(a[yi] != xi) {
					newPicture.set(nxi, yi, mPicture.get(xi, yi));
					nxi++;
				}
			}
		}
		
		mPicture = newPicture;
		mHeight  = mPicture.height();
		mWidth   = mPicture.width();
		initEnergy();
	}
	
	public static void main(String[] av)
	{
		{
			Picture pic = new Picture(3, 4);
			pic.set(0, 0, new Color(255,101,51));
			pic.set(0, 1, new Color(255,153,51));
			pic.set(0, 2, new Color(255,203,51));
			pic.set(0, 3, new Color(255,255,51));
			
			pic.set(1, 0, new Color(255, 101, 153));
			pic.set(1, 1, new Color(255,153,153));
			pic.set(1, 2, new Color(255,204,153));
			pic.set(1, 3, new Color(255,255,153));
	
			pic.set(2, 0, new Color(255, 101, 255));
			pic.set(2, 1, new Color(255,153,255));
			pic.set(2, 2, new Color(255,205,255));
			pic.set(2, 3, new Color(255,255,255));
			
	
			/*
			 (255, 101, 51)   	  (255, 101, 153)   	  (255, 101, 255)  
			  (255,153,51)   	  (255,153,153)   	  (255,153,255)  
			  (255,203,51)   	  (255,204,153)   	  (255,205,255)  
			  (255,255,51)   	  (255,255,153)   	  (255,255,255)
			  */  
			
			SeamCarver sc = new SeamCarver(pic);
			StdOut.println(sc.energy(1, 2));
			StdOut.println(sc.energy(1, 1));
		}		
		{
			Color[][] colors = new Color[][] {
				{ _c( 97, 82,107), _c(220,172,141), _c  	 (243, 71,205), _c  	 (129,173,222), _c  	 (225, 40,209), _c  	 ( 66,109,219) },
				{ _c	 (181, 78, 68), _c  	 ( 15, 28,216), _c  	 (245,150,150) , _c 	 (177,100,167)  , _c	 (205,205,177)  , _c	 (147, 58, 99) }, 
				{ _c	 (196,224, 21)  , _c	 (166,217,190)  , _c	 (128,120,162)  , _c	 (104, 59,110)  , _c	 ( 49,148,137)  , _c	 (192,101, 89) },
				{ _c	 ( 83,143,103) , _c 	 (110, 79,247) , _c 	 (106, 71,174) , _c 	 ( 92,240,205) , _c 	 (129, 56,146)  , _c	 (121,111,147) },
				{ _c	 ( 82,157,137) , _c 	 ( 92,110,129) , _c 	 (183,107, 80) , _c 	 ( 89, 24,217) , _c 	 (207, 69, 32)  , _c	 (156,112, 31) } 	
			};
			
			final int w = colors[0].length;
			final int h = colors.length;
			Picture pic = new Picture(w, h);
			
			for(int i = 0; i < h; i++)
				for(int j = 0; j < w; j++)
					pic.set(j, i, colors[i][j]);
			
			SeamCarver sc = new SeamCarver(pic);
			StdOut.println(sc.energy(1, 2));
			StdOut.println(sc.energy(1, 1));
			
			for(int i: sc.findVerticalSeam())
				StdOut.println(i);
			
			StdOut.println("Horizontal");
			for(int i: sc.findHorizontalSeam())
				StdOut.println(i);
			
			sc.removeHorizontalSeam(sc.findHorizontalSeam());
			
			sc.picture().save("1.png");
		}
	}
	
	private static Color _c(int r, int b, int g)
	{
		return new Color(r,b,g);
	}
}
